home *** CD-ROM | disk | FTP | other *** search
/ Languguage OS 2 / Languguage OS II Version 10-94 (Knowledge Media)(1994).ISO / gnu / libg_261.zip / libg_261 / libg++ / src / gen / AVLMap.ccP < prev    next >
Text File  |  1993-05-06  |  13KB  |  615 lines
  1. // This may look like C code, but it is really -*- C++ -*-
  2. /* 
  3. Copyright (C) 1988 Free Software Foundation
  4.     written by Doug Lea (dl@rocky.oswego.edu)
  5.  
  6. This file is part of the GNU C++ Library.  This library is free
  7. software; you can redistribute it and/or modify it under the terms of
  8. the GNU Library General Public License as published by the Free
  9. Software Foundation; either version 2 of the License, or (at your
  10. option) any later version.  This library is distributed in the hope
  11. that it will be useful, but WITHOUT ANY WARRANTY; without even the
  12. implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  13. PURPOSE.  See the GNU Library General Public License for more details.
  14. You should have received a copy of the GNU Library General Public
  15. License along with this library; if not, write to the Free Software
  16. Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
  17. */
  18.  
  19. #ifdef __GNUG__
  20. #pragma implementation
  21. #endif
  22. #include <stream.h>
  23. #include "<T>.<C>.AVLMap.h"
  24.  
  25.  
  26. /*
  27.  constants & inlines for maintaining balance & thread status in tree nodes
  28. */
  29.  
  30. #define AVLBALANCEMASK    3
  31. #define AVLBALANCED       0
  32. #define AVLLEFTHEAVY      1
  33. #define AVLRIGHTHEAVY     2
  34.  
  35. #define LTHREADBIT        4
  36. #define RTHREADBIT        8
  37.  
  38.  
  39. static inline int bf(<T><C>AVLNode* t)
  40. {
  41.   return t->stat & AVLBALANCEMASK;
  42. }
  43.  
  44. static inline void set_bf(<T><C>AVLNode* t, int b)
  45. {
  46.   t->stat = (t->stat & ~AVLBALANCEMASK) | (b & AVLBALANCEMASK);
  47. }
  48.  
  49.  
  50. static inline int rthread(<T><C>AVLNode* t)
  51. {
  52.   return t->stat & RTHREADBIT;
  53. }
  54.  
  55. static inline void set_rthread(<T><C>AVLNode* t, int b)
  56. {
  57.   if (b)
  58.     t->stat |= RTHREADBIT;
  59.   else
  60.     t->stat &= ~RTHREADBIT;
  61. }
  62.  
  63. static inline int lthread(<T><C>AVLNode* t)
  64. {
  65.   return t->stat & LTHREADBIT;
  66. }
  67.  
  68. static inline void set_lthread(<T><C>AVLNode* t, int b)
  69. {
  70.   if (b)
  71.     t->stat |= LTHREADBIT;
  72.   else
  73.     t->stat &= ~LTHREADBIT;
  74. }
  75.  
  76. /*
  77.  traversal primitives
  78. */
  79.  
  80.  
  81. <T><C>AVLNode* <T><C>AVLMap::leftmost()
  82. {
  83.   <T><C>AVLNode* t = root;
  84.   if (t != 0) while (t->lt != 0) t = t->lt;
  85.   return t;
  86. }
  87.  
  88. <T><C>AVLNode* <T><C>AVLMap::rightmost()
  89. {
  90.   <T><C>AVLNode* t = root;
  91.   if (t != 0) while (t->rt != 0) t = t->rt;
  92.   return t;
  93. }
  94.  
  95. <T><C>AVLNode* <T><C>AVLMap::succ(<T><C>AVLNode* t)
  96. {
  97.   <T><C>AVLNode* r = t->rt;
  98.   if (!rthread(t)) while (!lthread(r)) r = r->lt;
  99.   return r;
  100. }
  101.  
  102. <T><C>AVLNode* <T><C>AVLMap::pred(<T><C>AVLNode* t)
  103. {
  104.   <T><C>AVLNode* l = t->lt;
  105.   if (!lthread(t)) while (!rthread(l)) l = l->rt;
  106.   return l;
  107. }
  108.  
  109.  
  110. Pix <T><C>AVLMap::seek(<T&> key)
  111. {
  112.   <T><C>AVLNode* t = root;
  113.   if (t == 0)
  114.     return 0;
  115.   for (;;)
  116.   {
  117.     int cmp = <T>CMP(key, t->item);
  118.     if (cmp == 0)
  119.       return Pix(t);
  120.     else if (cmp < 0)
  121.     {
  122.       if (lthread(t))
  123.         return 0;
  124.       else
  125.         t = t->lt;
  126.     }
  127.     else if (rthread(t))
  128.       return 0;
  129.     else
  130.       t = t->rt;
  131.   }
  132. }
  133.  
  134.  
  135. /*
  136.  The combination of threads and AVL bits make adding & deleting
  137.  interesting, but very awkward.
  138.  
  139.  We use the following statics to avoid passing them around recursively
  140. */
  141.  
  142. static int _need_rebalancing;   // to send back balance info from rec. calls
  143. static <T>*   _target_item;     // add/del_item target
  144. static <T><C>AVLNode* _found_node; // returned added/deleted node
  145. static int    _already_found;   // for deletion subcases
  146.  
  147.  
  148. void <T><C>AVLMap:: _add(<T><C>AVLNode*& t)
  149. {
  150.   int cmp = <T>CMP(*_target_item, t->item);
  151.   if (cmp == 0)
  152.   {
  153.     _found_node = t;
  154.     return;
  155.   }
  156.   else if (cmp < 0)
  157.   {
  158.     if (lthread(t))
  159.     {
  160.       ++count;
  161.       _found_node = new <T><C>AVLNode(*_target_item, def);
  162.       set_lthread(_found_node, 1);
  163.       set_rthread(_found_node, 1);
  164.       _found_node->lt = t->lt;
  165.       _found_node->rt = t;
  166.       t->lt = _found_node;
  167.       set_lthread(t, 0);
  168.       _need_rebalancing = 1;
  169.     }
  170.     else
  171.       _add(t->lt);
  172.     if (_need_rebalancing)
  173.     {
  174.       switch(bf(t))
  175.       {
  176.       case AVLRIGHTHEAVY:
  177.         set_bf(t, AVLBALANCED);
  178.         _need_rebalancing = 0;
  179.         return;
  180.       case AVLBALANCED:
  181.         set_bf(t, AVLLEFTHEAVY);
  182.         return;
  183.       case AVLLEFTHEAVY:
  184.     {
  185.         <T><C>AVLNode* l = t->lt;
  186.         if (bf(l) == AVLLEFTHEAVY)
  187.         {
  188.           if (rthread(l))
  189.             t->lt = l;
  190.           else
  191.             t->lt = l->rt;
  192.           set_lthread(t, rthread(l));
  193.           l->rt = t;
  194.           set_rthread(l, 0);
  195.           set_bf(t, AVLBALANCED);
  196.           set_bf(l, AVLBALANCED);
  197.           t = l;
  198.           _need_rebalancing = 0;
  199.         }
  200.         else
  201.         {
  202.           <T><C>AVLNode* r = l->rt;
  203.           set_rthread(l, lthread(r));
  204.           if (lthread(r))
  205.             l->rt = r;
  206.           else
  207.             l->rt = r->lt;
  208.           r->lt = l;
  209.           set_lthread(r, 0);
  210.           set_lthread(t, rthread(r));
  211.           if (rthread(r))
  212.             t->lt = r;
  213.           else
  214.             t->lt = r->rt;
  215.           r->rt = t;
  216.           set_rthread(r, 0);
  217.           if (bf(r) == AVLLEFTHEAVY)
  218.             set_bf(t, AVLRIGHTHEAVY);
  219.           else
  220.             set_bf(t, AVLBALANCED);
  221.           if (bf(r) == AVLRIGHTHEAVY)
  222.             set_bf(l, AVLLEFTHEAVY);
  223.           else
  224.             set_bf(l, AVLBALANCED);
  225.           set_bf(r, AVLBALANCED);
  226.           t = r;
  227.           _need_rebalancing = 0;
  228.           return;
  229.         }
  230.     }
  231.       }
  232.     }
  233.   }
  234.   else
  235.   {
  236.     if (rthread(t))
  237.     {
  238.       ++count;
  239.       _found_node = new <T><C>AVLNode(*_target_item, def);
  240.       set_rthread(t, 0);
  241.       set_lthread(_found_node, 1);
  242.       set_rthread(_found_node, 1);
  243.       _found_node->lt = t;
  244.       _found_node->rt = t->rt;
  245.       t->rt = _found_node;
  246.       _need_rebalancing = 1;
  247.     }
  248.     else
  249.       _add(t->rt);
  250.     if (_need_rebalancing)
  251.     {
  252.       switch(bf(t))
  253.       {
  254.       case AVLLEFTHEAVY:
  255.         set_bf(t, AVLBALANCED);
  256.         _need_rebalancing = 0;
  257.         return;
  258.       case AVLBALANCED:
  259.         set_bf(t, AVLRIGHTHEAVY);
  260.         return;
  261.       case AVLRIGHTHEAVY:
  262.     {
  263.         <T><C>AVLNode* r = t->rt;
  264.         if (bf(r) == AVLRIGHTHEAVY)
  265.         {
  266.           if (lthread(r))
  267.             t->rt = r;
  268.           else
  269.             t->rt = r->lt;
  270.           set_rthread(t, lthread(r));
  271.           r->lt = t;
  272.           set_lthread(r, 0);
  273.           set_bf(t, AVLBALANCED);
  274.           set_bf(r, AVLBALANCED);
  275.           t = r;
  276.           _need_rebalancing = 0;
  277.         }
  278.         else
  279.         {
  280.           <T><C>AVLNode* l = r->lt;
  281.           set_lthread(r, rthread(l));
  282.           if (rthread(l))
  283.             r->lt = l;
  284.           else
  285.             r->lt = l->rt;
  286.           l->rt = r;
  287.           set_rthread(l, 0);
  288.           set_rthread(t, lthread(l));
  289.           if (lthread(l))
  290.             t->rt = l;
  291.           else
  292.             t->rt = l->lt;
  293.           l->lt = t;
  294.           set_lthread(l, 0);
  295.           if (bf(l) == AVLRIGHTHEAVY)
  296.             set_bf(t, AVLLEFTHEAVY);
  297.           else
  298.             set_bf(t, AVLBALANCED);
  299.           if (bf(l) == AVLLEFTHEAVY)
  300.             set_bf(r, AVLRIGHTHEAVY);
  301.           else
  302.             set_bf(r, AVLBALANCED);
  303.           set_bf(l, AVLBALANCED);
  304.           t = l;
  305.           _need_rebalancing = 0;
  306.           return;
  307.         }
  308.     }
  309.       }
  310.     }
  311.   }
  312. }
  313.  
  314.     
  315. <C>& <T><C>AVLMap::operator [] (<T&> item)
  316. {
  317.   if (root == 0)
  318.   {
  319.     ++count;
  320.     root = new <T><C>AVLNode(item, def);
  321.     set_rthread(root, 1);
  322.     set_lthread(root, 1);
  323.     return root->cont;
  324.   }
  325.   else
  326.   {
  327.     _target_item = &item;
  328.     _need_rebalancing = 0;
  329.     _add(root);
  330.     return _found_node->cont;
  331.   }
  332. }
  333.  
  334.  
  335. void <T><C>AVLMap::_del(<T><C>AVLNode* par, <T><C>AVLNode*& t)
  336. {
  337.   int comp;
  338.   if (_already_found)
  339.   {
  340.     if (rthread(t))
  341.       comp = 0;
  342.     else
  343.       comp = 1;
  344.   }
  345.   else 
  346.     comp = <T>CMP(*_target_item, t->item);
  347.   if (comp == 0)
  348.   {
  349.     if (lthread(t) && rthread(t))
  350.     {
  351.       _found_node = t;
  352.       if (t == par->lt)
  353.       {
  354.         set_lthread(par, 1);
  355.         par->lt = t->lt;
  356.       }
  357.       else
  358.       {
  359.         set_rthread(par, 1);
  360.         par->rt = t->rt;
  361.       }
  362.       _need_rebalancing = 1;
  363.       return;
  364.     }
  365.     else if (lthread(t))
  366.     {
  367.       _found_node = t;
  368.       <T><C>AVLNode* s = succ(t);
  369.       if (s != 0 && lthread(s))
  370.         s->lt = t->lt;
  371.       t = t->rt;
  372.       _need_rebalancing = 1;
  373.       return;
  374.     }
  375.     else if (rthread(t))
  376.     {
  377.       _found_node = t;
  378.       <T><C>AVLNode* p = pred(t);
  379.       if (p != 0 && rthread(p))
  380.         p->rt = t->rt;
  381.       t = t->lt;
  382.       _need_rebalancing = 1;
  383.       return;
  384.     }
  385.     else                        // replace item & find someone deletable
  386.     {
  387.       <T><C>AVLNode* p = pred(t);
  388.       t->item = p->item;
  389.       t->cont = p->cont;
  390.       _already_found = 1;
  391.       comp = -1;                // fall through below to left
  392.     }
  393.   }
  394.  
  395.   if (comp < 0)
  396.   {
  397.     if (lthread(t))
  398.       return;
  399.     _del(t, t->lt);
  400.     if (!_need_rebalancing)
  401.       return;
  402.     switch (bf(t))
  403.     {
  404.     case AVLLEFTHEAVY:
  405.       set_bf(t, AVLBALANCED);
  406.       return;
  407.     case AVLBALANCED:
  408.       set_bf(t, AVLRIGHTHEAVY);
  409.       _need_rebalancing = 0;
  410.       return;
  411.     case AVLRIGHTHEAVY:
  412.       {
  413.       <T><C>AVLNode* r = t->rt;
  414.       switch (bf(r))
  415.       {
  416.       case AVLBALANCED:
  417.         if (lthread(r))
  418.           t->rt = r;
  419.         else
  420.           t->rt = r->lt;
  421.         set_rthread(t, lthread(r));
  422.         r->lt = t;
  423.         set_lthread(r, 0);
  424.         set_bf(t, AVLRIGHTHEAVY);
  425.         set_bf(r, AVLLEFTHEAVY);
  426.         _need_rebalancing = 0;
  427.         t = r;
  428.         return;
  429.       case AVLRIGHTHEAVY:
  430.         if (lthread(r))
  431.           t->rt = r;
  432.         else
  433.           t->rt = r->lt;
  434.         set_rthread(t, lthread(r));
  435.         r->lt = t;
  436.         set_lthread(r, 0);
  437.         set_bf(t, AVLBALANCED);
  438.         set_bf(r, AVLBALANCED);
  439.         t = r;
  440.         return;
  441.       case AVLLEFTHEAVY:
  442.     {
  443.         <T><C>AVLNode* l = r->lt;
  444.         set_lthread(r, rthread(l));
  445.         if (rthread(l))
  446.           r->lt = l;
  447.         else
  448.           r->lt = l->rt;
  449.         l->rt = r;
  450.         set_rthread(l, 0);
  451.         set_rthread(t, lthread(l));
  452.         if (lthread(l))
  453.           t->rt = l;
  454.         else
  455.           t->rt = l->lt;
  456.         l->lt = t;
  457.         set_lthread(l, 0);
  458.         if (bf(l) == AVLRIGHTHEAVY)
  459.           set_bf(t, AVLLEFTHEAVY);
  460.         else
  461.           set_bf(t, AVLBALANCED);
  462.         if (bf(l) == AVLLEFTHEAVY)
  463.           set_bf(r, AVLRIGHTHEAVY);
  464.         else
  465.           set_bf(r, AVLBALANCED);
  466.         set_bf(l, AVLBALANCED);
  467.         t = l;
  468.         return;
  469.     }
  470.       }
  471.     }
  472.     }
  473.   }
  474.   else
  475.   {
  476.     if (rthread(t))
  477.       return;
  478.     _del(t, t->rt);
  479.     if (!_need_rebalancing)
  480.       return;
  481.     switch (bf(t))
  482.     {
  483.     case AVLRIGHTHEAVY:
  484.       set_bf(t, AVLBALANCED);
  485.       return;
  486.     case AVLBALANCED:
  487.       set_bf(t, AVLLEFTHEAVY);
  488.       _need_rebalancing = 0;
  489.       return;
  490.     case AVLLEFTHEAVY:
  491.       {
  492.       <T><C>AVLNode* l = t->lt;
  493.       switch (bf(l))
  494.       {
  495.       case AVLBALANCED:
  496.         if (rthread(l))
  497.           t->lt = l;
  498.         else
  499.           t->lt = l->rt;
  500.         set_lthread(t, rthread(l));
  501.         l->rt = t;
  502.         set_rthread(l, 0);
  503.         set_bf(t, AVLLEFTHEAVY);
  504.         set_bf(l, AVLRIGHTHEAVY);
  505.         _need_rebalancing = 0;
  506.         t = l;
  507.         return;
  508.       case AVLLEFTHEAVY:
  509.         if (rthread(l))
  510.           t->lt = l;
  511.         else
  512.           t->lt = l->rt;
  513.         set_lthread(t, rthread(l));
  514.         l->rt = t;
  515.         set_rthread(l, 0);
  516.         set_bf(t, AVLBALANCED);
  517.         set_bf(l, AVLBALANCED);
  518.         t = l;
  519.         return;
  520.       case AVLRIGHTHEAVY:
  521.     {
  522.         <T><C>AVLNode* r = l->rt;
  523.         set_rthread(l, lthread(r));
  524.         if (lthread(r))
  525.           l->rt = r;
  526.         else
  527.           l->rt = r->lt;
  528.         r->lt = l;
  529.         set_lthread(r, 0);
  530.         set_lthread(t, rthread(r));
  531.         if (rthread(r))
  532.           t->lt = r;
  533.         else
  534.           t->lt = r->rt;
  535.         r->rt = t;
  536.         set_rthread(r, 0);
  537.         if (bf(r) == AVLLEFTHEAVY)
  538.           set_bf(t, AVLRIGHTHEAVY);
  539.         else
  540.           set_bf(t, AVLBALANCED);
  541.         if (bf(r) == AVLRIGHTHEAVY)
  542.           set_bf(l, AVLLEFTHEAVY);
  543.         else
  544.           set_bf(l, AVLBALANCED);
  545.         set_bf(r, AVLBALANCED);
  546.         t = r;
  547.         return;
  548.     }
  549.       }
  550.       }
  551.     }
  552.   }
  553. }
  554.  
  555.         
  556.  
  557. void <T><C>AVLMap::del(<T&> item)
  558. {
  559.   if (root == 0) return;
  560.   _need_rebalancing = 0;
  561.   _already_found = 0;
  562.   _found_node = 0;
  563.   _target_item = &item;
  564.   _del(root, root);
  565.   if (_found_node)
  566.   {
  567.     delete(_found_node);
  568.     if (--count == 0)
  569.       root = 0;
  570.   }
  571. }
  572.  
  573. void <T><C>AVLMap::_kill(<T><C>AVLNode* t)
  574. {
  575.   if (t != 0)
  576.   {
  577.     if (!lthread(t)) _kill(t->lt);
  578.     if (!rthread(t)) _kill(t->rt);
  579.     delete t;
  580.   }
  581. }
  582.  
  583.  
  584. <T><C>AVLMap::<T><C>AVLMap(<T><C>AVLMap& b) :<T><C>Map(b.def)
  585. {
  586.   root = 0;
  587.   count = 0;
  588.   for (Pix i = b.first(); i != 0; b.next(i)) 
  589.     (*this)[b.key(i)] = b.contents(i);
  590. }
  591.  
  592.  
  593. int <T><C>AVLMap::OK()
  594. {
  595.   int v = 1;
  596.   if (root == 0) 
  597.     v = count == 0;
  598.   else
  599.   {
  600.     int n = 1;
  601.     <T><C>AVLNode* trail = leftmost();
  602.     <T><C>AVLNode* t = succ(trail);
  603.     while (t != 0)
  604.     {
  605.       ++n;
  606.       v &= <T>CMP(trail->item, t->item) < 0;
  607.       trail = t;
  608.       t = succ(t);
  609.     }
  610.     v &= n == count;
  611.   }
  612.   if (!v) error("invariant failure");
  613.   return v;
  614. }
  615.